#
# @lc app=leetcode.cn id=34 lang=python3
#
# [34] 在排序数组中查找元素的第一个和最后一个位置
#

# @lc code=start
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        return [self.searchStart(nums, target), self.searchEnd(nums, target)]
        

    def searchStart(self, nums, target):
        if not nums:
            return -1

        l, r = 0, len(nums) - 1
        
        while l <= r:
            mid = l + ((r - l) >> 1)
            # 此时target在左边
            if nums[mid] > target:
                r = mid - 1
            # 此时target在右边
            elif nums[mid] < target:
                l = mid + 1
            # target == nums[mid]
            else:
                # 目标值的起始点
                if mid == 0 or nums[mid - 1] != target:
                    return mid
                else:
                    r = mid - 1
        return -1


    def searchEnd(self, nums, target):
        if not nums:
            return -1

        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + ((r - l) >> 1)
            # 此时target在左边
            if nums[mid] > target:
                r = mid - 1
            # 此时target在右边
            elif nums[mid] < target:
                l = mid + 1
            # target == nums[mid]
            else:
                # 目标值的终点
                if mid == len(nums) - 1 or nums[mid + 1] != target:
                    return mid
                else:
                    l = mid + 1
        
        return -1
# @lc code=end